import math
import tranfer
#多点路径规划函数，输入点的数量，输入的点的信息，和经过经纬度查询后的点的经纬度信息
def gh(m,df,cf):
    n = int(m)
    x = []
    y = []
    b = []
    results = []
    road=[]
    for i in range(0, n):   #将一维列表进行转化，得到二维列表
        road.append([])

    for i in range(0, n):
        for j in range(0, n):
            road[i].append(0)   #将二维列表内的数据全部初始化为0

    for i in range(0,n): #调用tranfer函数中的transfers函数，由于经过运算得到的敬经纬度信息是以字符串形式存储在列表中，需要转化为数的形式
        mid=tranfer.transfers(df[i])#对经过初步转化的经纬度信息进行存储，从类似['1,2','3,4']的信息转化为[1,2,3,4]的形式
        x.append(tranfer.transferd(mid[0])/1000)#对经纬度进行进一步转化，由于经纬度信息保留到小数点后六位，因此先去除小数点再缩小1000倍，相当于最终扩大1000倍方便运算
        y.append(tranfer.transferd(mid[1])/1000)
        b.append(0) #对数组b进行初始化为0


    b[0]=1 #存储路线
    i1=0    #初始化i1的值方便进行while运算
    while i1 < n:
        for j1 in range(0, n):
            xr = x[i1] - x[j1]
            yr = y[i1] - y[j1]
            # print(x[i],y[i])
            r = xr * xr + yr * yr
            r = math.sqrt(r)

            road[i1][j1] = r #取得每两点间的距离并存入road数组中
            print(i1, j1)
        i1 = i1 + 1

    l=[] #存储路线
    l.append(0)

    next=0 #next用于存储下一个目标点
    now=0   #now用于存储现在的所在点

    for i3 in range(1,n):
        min=10000 #初始化min
        for j3 in range(1,n):
            if road[now][j3]<min and b[j3] == 0: #j点为距离now点最近的且没有遍历过的点
                min=road[now][j3]
                next=j3

        l.append(next) #存储入路径数组
        now=next
        b[next]=1   #标记遍历过的点


    for i4 in range(0, n): #对输入点的信息排序成最终的结果顺序
        results.append(cf[l[i4]])
    return results



